import java.util.*;

public class Leet312 {
    public static void main(String[] args) {
        Leet312 l = new Leet312();
        System.out.println(l.maxCoins(new int[]{7,9,8,0,7,1,3,5,5,2,3}));
    }
    static int max;
    public int maxCoins(int[] nums) {
        if (nums.length==1)
            return nums[0];
        max = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for (int num : nums)
            list.add(num);
        for (int i = 0; i < list.size(); i++) {
            int num = 0;
            if (i==0)
                num+=list.get(i)*list.get(i+1);
            else if(i==list.size()-1)
                num+=list.get(i)*list.get(i-1);
            else num+=list.get(i)*list.get(i-1)*list.get(i+1);
            int temp = list.remove(i);
            dfs(num,list);
            list.add(i,temp);
        }
        return max;
    }
    void dfs(int num,LinkedList<Integer> list){
        if (list.size()==0){
            max = Math.max(max,num);
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            if (i==0&&list.size()==1)
                num+=list.get(i);
            else if (i==0)
                num+=list.get(i)*list.get(i+1);
            else if(i==list.size()-1)
                num+=list.get(i)*list.get(i-1);
            else num+=list.get(i)*list.get(i-1)*list.get(i+1);
            int temp = list.remove(i);
            dfs(num,list);
            list.add(i,temp);
            if (i==0&&list.size()==1)
                num-=list.get(i);
            else if (i==0)
                num-=list.get(i)*list.get(i+1);
            else if(i==list.size()-1)
                num-=list.get(i)*list.get(i-1);
            else num-=list.get(i)*list.get(i-1)*list.get(i+1);
        }
    }
}
